# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        node_list = []
        if not pRootOfTree:
            return None
        def getmidsort(pRootOfTree, nodelist):
            if not pRootOfTree:
                return None
            getmidsort(pRootOfTree.left, node_list)
            node_list.append(pRootOfTree)
            getmidsort(pRootOfTree.right, node_list)
        getmidsort(pRootOfTree, node_list)
        if len(node_list) == 1:
            return node_list[0]
        for i in range(len(node_list)):
            if i == 0:
                node_list[i].left = None
                node_list[i].right = node_list[i+1]
            elif i == len(node_list) -1:
                node_list[i].left = node_list[i-1]
                node_list[i].right = None
            else:
                node_list[i].left = node_list[i-1]
                node_list[i].right = node_list[i+1]
        return node_list[0]

class Solution:
    def Convert(self, pRootOfTree):
        # 该函数返回的是最左边的点，用递归一定要想明白返回的值是什么
        if not pRootOfTree:
            return None
        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree
        left = self.Convert(pRootOfTree.left)
        p = left
        while p and p.right:
            p = p.right
        if left:
            p.right = pRootOfTree
            pRootOfTree.left = p
        right = self.Convert(pRootOfTree.right)
        if right:
            right.left = pRootOfTree
            pRootOfTree.right = right
        return left if left else pRootOfTree






